package _3sort.src;


/**
 * @className: _4mergeSort_problem
 * @description:
 * @author: myself
 * @date: 2025/7/15 22:31
 * @version: 0.1
 * @since: JDK17
 */

/*类似小和问题：
 * 在一个数组中,每一个数左边比当前数小的数累加起来，叫做这个数组的小和。
 * 例如：[1,3,4,2,5]
 * 比1小的没有
 * 比3小的左侧有一个1，sum=1
 * 比4小的左侧有1，3，sum=1+1=3=5
 * 比2小的左侧有1，sum=5+1=6
 * 比5小的左侧有1.3.4.2，sum=6+1+3+4+2=16
 * ...
 * 结果16
 * */

    /*问题：求逆序对
    * 即前者大于后者
    * */
public class _4mergeSort_problem2 {
    public static int sum = 0;

    public static int process(int[] nums, int n, int m) {
        if (n == m) {
            return 0;
        }
        int mid = (n + m) >>> 1;
        return process(nums, n, mid) + process(nums, mid + 1, m) + merge(nums, n, mid, m);
    }

    public static int merge(int[] nums, int n, int m, int l) {
        int[] temp = new int[l - n + 1];//创建一个空白数组，用于转移
        int p1 = n;
        int p2 = m + 1;
        int i = 0;
        while (p1 <= m && p2 <= l) {
            sum += nums[p1] < nums[p2] ? (l - p2 + 1) * nums[p1] : 0;
            System.out.println("有序对"+nums[p2]+": "+nums[p1]);
            temp[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= m) {
            temp[i++] = nums[p1++];
        }
        while (p2 <= l) {
            temp[i++] = nums[p2++];
        }
        System.arraycopy(temp, 0, nums, n, temp.length);
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 2, 5};
        process(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        System.out.println(sum);
    }
}
